//    Copyright (C) Kherty.  All rights reserved.
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;

namespace OpenLS.Spreadsheet
{
    class Node<T>
    {
        public Node(T t)
        {
            _data = t;
        }
        private readonly T _data;
        public T Data
        {
            get { return _data; }
        }

        private readonly HashListNoDuplicate<Node<T>> _children = new HashListNoDuplicate<Node<T>>();
        public HashListNoDuplicate<Node<T>> Children
        {
            get { return _children; }
        }

        private readonly HashListNoDuplicate<Node<T>> _parents = new HashListNoDuplicate<Node<T>>();
        public HashListNoDuplicate<Node<T>> Parents
        {
            get { return _parents; }
        }


        internal void RemoveChildNode(Node<T> childNode)
        {
            childNode.Parents.Remove(this);
            Children.Remove(childNode);
        }

        internal void AddParent(Node<T> parent)
        {
            if (!Parents.Contains(parent))
                Parents.Add(parent);
        }

        internal void AddChild(Node<T> child)
        {
            if (!Children.Contains(child))
                Children.Add(child);
        }

#if DEBUG
        [ContractInvariantMethod]
        private void ObjectInvariant()
        {
            Contract.Invariant(Enumerable.All(Children, node => node.Parents.Contains(this)));
            Contract.Invariant(Enumerable.All(Parents, node => node.Children.Contains(this)));
        }
#endif


        internal List<Node<T>> GetDescendants()
        {
            List<Node<T>> result = new List<Node<T>>();
            Dictionary<Node<T>, Node<T>> alreadyProcessed = new Dictionary<Node<T>, Node<T>>();
            Queue<Node<T>> toProcess = new Queue<Node<T>>();
            foreach (Node<T> child in Children)
                toProcess.Enqueue(child);
            while (toProcess.Count > 0)
            {
                Node<T> n = toProcess.Dequeue();
                if (alreadyProcessed.ContainsKey(n))
                    continue;
                alreadyProcessed.Add(n, n);
                result.Add(n);
                foreach (Node<T> child in n.Children)
                    toProcess.Enqueue(child);
            }
            return result;
        }
        List<Node<T>> GetAncestors()
        {
            List<Node<T>> result = new List<Node<T>>();
            Dictionary<Node<T>, Node<T>> alreadyProcessed = new Dictionary<Node<T>, Node<T>>();
            Queue<Node<T>> toProcess = new Queue<Node<T>>();
            foreach (Node<T> child in Parents)
                toProcess.Enqueue(child);
            while (toProcess.Count > 0)
            {
                Node<T> n = toProcess.Dequeue();
                if (alreadyProcessed.ContainsKey(n))
                    continue;
                alreadyProcessed.Add(n, n);
                result.Add(n);
                foreach (Node<T> child in n.Parents)
                    toProcess.Enqueue(child);
            }
            return result;
        }
        internal bool HasChildCycle()
        {
            foreach (Node<T> n in GetDescendants())
                if (n == this)
                    return true;
            return false;
        }
        internal bool HasParentCycle()
        {
            foreach (Node<T> n in GetAncestors())
                if (n == this)
                    return true;
            return false;
        }
    }
}
